KM 算法用来求二分图最大权完美匹配。当二分图两侧点数不同时，需要将较少部分的点补足，然后将不存在的边视为边权为 −∞-\infty−∞。
下设总点数为 2n2n2n，其中左部点编号为 1∼n1 \sim n1∼n，右部点编号为 n+1∼2nn + 1 \sim 2nn+1∼2n。下面认为图是完全二分图，不存在的边边权为 −∞-\infty−∞。
我们给每个点一个点权 lil _ ili，称之为顶标。称一组顶标是可行顶标当且仅当对于所有边 (u,v)(u, v)(u,v) 都满足 wu,v≤lu+lvw _ {u, v} \le l _ u + l _ vwu,v≤lu+lv。
我们定义相等子图是原图的一个子图 G′=(V,E′)G' = (V, E')G′=(V,E′)，使得 ∀(u,v)∈E′,wu,v=lu+lv\forall (u, v) \in E', w _ {u, v} = l _ u + l _ v∀(u,v)∈E′,wu,v=lu+lv。
定理：若一张图的相等子图存在完美匹配，则该匹配即为原图的最大权完美匹配。
证...
约定：本文中用 u→vu \to vu→v 表示从 uuu 通过一条边直接走到 vvv，u⇝vu \rightsquigarrow vu⇝v 表示 uuu 通过某条路径走到 vvv。
支配关系与支配点
对于一张有向图和一个起始点 sss，我们定义 uuu 支配 vvv 当且仅当所有 sss 到 vvv 的路径都经过 uuu，记做 udomvu \mathbin{\mathrm{dom}} vudomv。
方便起见，我们认为 sss 可以到达图上每一个点。
若 udomvu \mathbin{\mathrm{dom}} vudomv，则我们认为 uuu 是 vvv 的一个支配点。每个点都是自己的支配点，sss 是所有点的支配点。
引理 1：支配关系是偏序关系。
根据定义有自反性，反对称性和传递性也是好证的。
引理 2：若 udomw,vdomwu \mathbin{\mathrm{dom}} w, v \mathbin{\mathrm{dom}} wudomw,vdomw，则 udomvu \mathbin{\mathrm{dom}} vudomv 或 vdomuv \ma...
符号与约定
下文默认图是连通的。
子图：点集与边集都是原图点集与边集的子集的图。
导出子图：一个点集的导出子图是该点集与所有两个端点均在该点集内的边构成的边集构成的子图。
团：完全子图。
极大团：不是其他团的子图的团。
最大团：点数最大的团。
团数：最大团的点数。
最小染色：使用最少的颜色给点染色使得任意一条边的两个端点颜色不同。
色数：最小染色的颜色数。
最大独立集：最大的点集使得其中任意两个点之间没有边。
最小团覆盖：用最少的团覆盖所有点。
弦：连接环上两个不相邻的点的边。
弦图：任意一个大小大于 333 的环都有一个弦的图。
弦图的性质
性质 1：团数小于等于色数。
考虑对最大团染色至少需要团数种颜色。
性质 2：最大独立集小于等于最小团覆盖。
每个团中至多选择一个点。
以上两个性质在普通图上也存在。
性质 3：弦图的导出子图一定是弦图。
考虑到若导出子图上存在无弦环，其在原图上也存在。
点割集
我们称弦图上任意两点 u,vu, vu,v 的点割集是满足删去其中的点后 u,vu, vu,v 不连通的集合。
引理 1：弦图上任意两点 u,vu, vu,...
前置知识
笛卡尔积
对于两个集合 X,YX, YX,Y，定义它们的笛卡尔积为 X×Y={(x,y)∣x∈X,y∈Y}X \times Y = \{(x, y) \mid x \in X, y \in Y\}X×Y={(x,y)∣x∈X,y∈Y}。
对于任意集合 AAA，定义 A1=AA ^ 1 = AA1=A，An=An−1×A(n∈N,n>1)A ^ n = A ^ {n - 1} \times A(n \in \N, n > 1)An=An−1×A(n∈N,n>1)。
二元关系
对于两个集合 X,YX, YX,Y，定义 XXX 到 YYY 的二元关系 RRR 为 X×YX \times YX×Y 的子集。对于 x∈X,y∈Yx \in X, y \in Yx∈X,y∈Y，记 xRyx\mathrel{R}yxRy 当且仅当 (x,y)∈R(x, y) \in R(x,y)∈R。
如果 Y=XY = XY=X，则可以称 RRR 是 XXX 上的二元关系。
等价关系
对于集合 XXX 上的二元关系 RRR，定义其为等价关系，当且仅当其满足：
自反性（r...
问题概述
给你一个正整数 nnn（1≤n≤2×1051 \le n \le 2 \times 10 ^ 51≤n≤2×105），求一个长度为 nnn 的 01 串，使得其本质不同的子串数量在所有 2n2 ^ n2n 个长度为 nnn 的 01 串中最多。
答案上界
我们考虑字符串的长度 iii，显然在长度为 nnn 的字符串中，本质不同的长度为 iii 的字符串个数上界为 min{2i,n−i+1}\min\left\{2 ^ i, n - i + 1\right\}min{2i,n−i+1}，所以答案上界为 ∑i=1nmin{2i,n−i+1}\sum _ {i = 1} ^ n \min\left\{2 ^ i, n - i + 1\right\}∑i=1nmin{2i,n−i+1}。
对于 n = 2 ^ k + k - 1
这里我们引入一个名为 De Bruijn Graph 的特殊的有向图。
定义 De Bruijn Graph 为一个有 knk ^ nkn 个点的有向图，每个点为一个由 kkk 种元素组成的有序 nnn 元组。当且仅当两个点 u,vu, ...
希望不会咕咕咕……
有些题 LOJ 上没有就不写了。
JOISC 2014
Day1T1 バス通学
答案显然只能是以 111 为起点的边的起始时间。
考虑将每个点的出边按起始时间从大到小排序，则对于每个到达时间，可以走的边都是一个前缀。
我们考虑对于每个答案跑最短路，发现复杂度爆炸。
但是排序后前面的答案能走的边后面的答案一定能走，于是我们考虑在之前的基础上跑最短路。具体地，我们对于每个点记录一个指针表示当前枚举到了第几条出边，显然指针之前的边没必要重新走一遍。这样每条边至多被使用一次，时间复杂度为 O(mlogm)O(m \log m)O(mlogm)。
最后对于每组询问二分即可得到答案。
提交记录
Day1T2 たのしい家庭菜園
显然最终序列一定是先一段单调不降再一段单调不升。
对于没有相同元素的情况，有一个显然的贪心：每次将最小的元素移到最左或最右（选择距离较短的），然后变成一个子问题。
考虑维护每个元素的实际位置，则移到最左对应前缀 +1+ 1+1，移到最前对应后缀 −1- 1−1，树状数组维护即可。
对于有相同元素的情况，每次移动距离最短的那个即可。
提交记录
...
符号及基本定义及约定
整除、取模、质数、算术基本定理等的定义。这部分直接 skip 了。
以下无特殊说明则默认变量为正整数，函数为数论函数。
以下用 P\mathbb{P}P 表示素数集合。
数论函数
定义域为正整数的函数被称为数论函数。
积性函数
若数论函数 f(x)f(x)f(x) 满足对于任意 a⊥ba \bot ba⊥b，有 f(ab)=f(a)f(b)f(ab) = f(a) f(b)f(ab)=f(a)f(b)，则称 f(x)f(x)f(x) 为积性函数。
若数论函数 f(x)f(x)f(x) 满足对于任意 a,ba, ba,b，有 f(ab)=f(a)f(b)f(ab) = f(a) f(b)f(ab)=f(a)f(b)，则称 f(x)f(x)f(x) 为完全积性函数。
性质
若 f(x)f(x)f(x) 和 g(x)g(x)g(x) 均为积性函数，则以下函数也是积性函数。
h(x)=f(xp)h(x) = f(x ^ p)h(x)=f(xp)。
h(x)=fp(x)h(x) = f ^ p(x)h(x)=fp(x)。
h(x)=f(x)g(x)h...
前言
会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是 Ad-hoc 或构造或结论题，标 + 的是比较有意思的思维题。根据牛牛程度会增减数量。
CF1137C Museums Tour [!]
tags: 图论, Tarjan, 拓扑排序\verb|tags: 图论, Tarjan, 拓扑排序|tags: 图论, Tarjan, 拓扑排序
建分层图，然后缩点，对于每个强连通分量求出其中有多少个地方。
然后直接拓扑排序求最长路就是答案。
问题在于为什么同一天不会被重复统计。
发现天数是循环的，也就是说如果某个城市第 xxx 天和第 x+yx + yx+y 天不在同一个强连通分量里，且能从第 xxx 天到达第 x+yx + yx+y 天，那一定能从第 x+yx + yx+y 天到达第 x+2yx + 2yx+2y 天，以此类推，一定能到达 (x+dy) mod d=x(x + dy) \bmod d = x(x+dy)modd=x 天，所以 xxx 和 x+yx + yx+y 一定在同一个强连通分量里。
CF1137E Tr...
前言
会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是 Ad-hoc 或构造或结论题，标 + 的是比较有意思的思维题。根据牛牛程度会增减数量。
CF1037G A Game on Strings [!!!]
观察发现，如果某次我选择了字符 ccc，则剩下的子串要么左边是 ccc，要么右边是 ccc。
也就是说，对于每个字符 ccc，设其出现的位置为 posc,1,posc,2,…,posc,kpos _ {c, 1}, pos _ {c, 2}, \ldots, pos _ {c, k}posc,1,posc,2,…,posc,k，那么有用的串就是所有 sposc,i,posc,i+1s _ {pos _ {c, i}, pos _ {c, i + 1}}sposc,i,posc,i+1 及其所有前缀和后缀。这样的串的个数为 O(n∣Σ∣)O(n \left|\Sigma\right|)O(n∣Σ∣)。
我们考虑预处理出所有有用的串的 SG 函数。
考虑将所有串按长度排序，对于每个串暴力转移。
很可惜，这样复杂...